package com.AC.ACSougou;

import org.junit.Test;

import java.util.HashSet;
import java.util.LinkedList;

public class test3 {
    HashSet<String> set = new HashSet<>();

    String password;

    public long getPasswordCount (String password) {
        this.password = password;
        set.add(password);
        dfs(new LinkedList<>(), 0);
        return set.size() - 1;
    }

    public void dfs(LinkedList<Character> strb, int index){

        if(index == 0){
            for(int i = 1; i<= 9; i++){
                strb.push(intToChar(i));
                dfs(strb, index + 1);
                strb.pollLast();
            }
            return;
        }

        if(strb.size()  == this.password.length() ){
            set.add(strb.toString());
            return;
        }



        for(int i = index; i<password.length(); i++){
            int last = strb.peekLast();
            int cur = charToInt(password.charAt(i));
            if(((last + cur) & 0x1) != 0){
                char a = intToChar((last + cur + 1) / 2) ;
                char b = intToChar((last + cur) / 2);

                strb.push(a);
                dfs(strb, i + 1);
                strb.pollLast();

                strb.push(b);
                dfs(strb, i + 1);
                strb.pollLast();
            }else{
                strb.push(intToChar((last + cur) / 2));
                dfs(strb, i + 1);
                strb.pollLast();
            }
        }
    }

    public char intToChar(int c){
        return String.valueOf(c).charAt(0);
    }

    public int charToInt(char c){
        return c - '0';
    }

    @Test
    public void test(){
        System.out.println(getPasswordCount("123"));
//        System.out.println(intToChar(2));
//        System.out.println(charToInt('2'));
    }

}
